//----------------单源bfs最短路问题-----------
//迷宫中离入口最近的出口
class Solution {
public:
    using PII = pair<int,int>;
    int dx[4] = {-1,1,0,0} , dy[4] = {0,0,-1,1};
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        //保存一下走过的路径
        int m = maze.size() , n = maze[0].size();
        vector<vector<bool>> hash(m,vector<bool>(n,false));
        queue<PII> q;
        q.push({entrance[0],entrance[1]});
        hash[entrance[0]][entrance[1]] = true;
        int ret = -1;
        int step = -1;
        while(!q.empty())
        {
            int size = q.size();
            step++;
            for(size_t k = 0 ; k < size ; ++k)
            {
                auto [a,b] = q.front();
                if((a != entrance[0] || b != entrance[1]) && (a == m-1 || b == n-1 || a == 0 || b == 0)) 
                {
                    ret = step;
                    return ret;
                }
                q.pop();
                for(size_t i = 0 ; i < 4 ; ++i)
                {
                    int y = a + dy[i] , x = b + dx[i];
                    if(y >= 0 && x >= 0 && y < m && x < n && maze[y][x] == '.' && hash[y][x] == false)
                    {
                        q.push({y,x});
                        hash[y][x] = true;
                    }
                }
            }

        }
        return ret;
        
    }
};

//最小基因变化
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        queue<string> q;
        unordered_set<string> hash;
        int ret = -1;
        int step = 0;
        if(startGene == endGene) return 0;
        for (auto str : bank) {
            int count = 0;
            for (size_t i = 0; i < 8; ++i) {
                if (str[i] != startGene[i])
                    count++;
            }
            if (count == 1) {
                hash.insert(str);
                q.push(str);
            }
        }
        while (!q.empty()) {
            int size = q.size();
            ++step;
            for (size_t i = 0; i < size; ++i) {
                auto headstr = q.front();
                q.pop();

                if (headstr == endGene) {
                    ret = step;
                    return ret;
                }

                for (auto str : bank) {
                    if (hash.find(str) == hash.end()) {
                        int count = 0;
                        for (size_t i = 0; i < 8; ++i) {
                            if (str[i] != headstr[i])
                                count++;
                        }
                        if (count == 1) {
                            hash.insert(str);
                            q.push(str);
                        }
                    }
                }
            }
        }
        return ret;
    }
};

//单词接龙
class Solution {
public:
    int ladderLength(string beginWord, string endWord,
                     vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        if(!hash.count(endWord)) return 0;
        queue<string> q;
        q.push(beginWord);
        int ret = 0;
        while (!q.empty()) {
            int size = q.size();
            ret++;
            for (size_t i = 0; i < size; ++i) 
            {
                auto str = q.front();
                q.pop();
                if (str == endWord)
                    return ret;
                for(size_t i = 0 ; i < str.size() ; ++i)
                {
                    for(char ch = 'a' ; ch <= 'z' ; ++ch)
                    {
                        char temp = str[i];
                        str[i] = ch;
                        if(hash.count(str))
                        {
                            hash.erase(str);
                            q.push(str);
                        }
                        str[i] = temp;
                    }
                }
            }
        }
        return 0;
    }
};

//为高尔夫比赛砍树
class Solution {
public:
    int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
    int maze(vector<vector<int>>& forest, int sr, int sc, int dstr, int dstc) {
        bool vis[51][51] = {false};
        int m = forest.size() , n = forest[0].size();
        queue<pair<int,int>> q;
        q.push({sr,sc});
        int ret = 0;
        while (!q.empty()) {
            int size = q.size();
            ++ret;
            for (size_t j = 0; j < size; ++j) {
                auto [row, col] = q.front();
                q.pop();
                if (row == dstr && col == dstc)
                {
                    return ret-1;
                }
                for (size_t k = 0; k < 4; ++k) {
                    int y = row + dy[k], x = col + dx[k];
                    if (y >= 0 && x >= 0 && y < m && x < n &&
                        forest[y][x] != 0 && vis[y][x] == false) {
                        vis[y][x] = true;
                        q.push({y, x});
                    }
                }
            }
        }
        return -1;
    }
        int cutOffTree(vector<vector<int>> & forest) {
            int m = forest.size(), n = forest[0].size();
            vector<pair<int, int>> v;
            for (size_t i = 0; i < m; ++i) {
                for (size_t j = 0; j < n; ++j) {
                    if (forest[i][j] > 1) {
                        v.push_back({i, j});
                    }
                }
            }
            sort(v.begin(), v.end(), [&](pair<int, int> p1, pair<int, int> p2) {
                return forest[p1.first][p1.second] <
                       forest[p2.first][p2.second];
            });
            // 转化为迷宫问题
            queue<pair<int, int>> q;
            q.push({0, 0});
            int ret = 0;
            int sr = 0 , sc = 0;
            for (size_t i = 0; i < v.size(); ++i) {
                int dstr = v[i].first, dstc = v[i].second;
                int n = maze(forest,sr,sc,dstr,dstc);
                if(n == -1) return -1;
                ret += n;
                sr = dstr;
                sc = dstc;
            }
            return ret;
        }
};

//----------------多源bfs最短路问题-----------
//矩阵
class Solution {
public:
    using PII = pair<int, int>;
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        int m = mat.size(), n = mat[0].size();
        queue<PII> q;
        vector<vector<int>> ret(m, vector<int>(n, -1));
        for (size_t i = 0; i < m; ++i) 
        {
            for (size_t j = 0; j < n; ++j) 
            {
                // 多源BFS
                if (mat[i][j] == 0) 
                {
                    ret[i][j]++;
                    q.push({i, j});
                }
            }
        }
        while (!q.empty()) 
        {
            auto [a, b] = q.front();
            q.pop();
            for (size_t k = 0; k < 4; ++k) 
            {
                int y = a + dy[k], x = b + dx[k];
                if (y >= 0 && x >= 0 && y < m && x < n && ret[y][x] == -1) 
                {
                    q.push({y, x});
                    ret[y][x] = ret[a][b] + 1;
                }
            }
        }
        return ret;
    }
};

//飞地的数量
class Solution {
public:
    using PII = pair<int,int>;
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int numEnclaves(vector<vector<int>>& grid) {
        //先看边界
        int m = grid.size() , n = grid[0].size();
        vector<vector<bool>> vis(m,vector<bool>(n));
        //先找出边界
        queue<PII> q;
        for(size_t i = 0 ; i < m ; ++i)
        {
            if(grid[i][0] == 1)
            {
                q.push({i,0});
                vis[i][0] = true;
            }
            if(grid[i][n-1] == 1)
            {
                q.push({i,n-1});
                vis[i][n-1] = true;
            }
        }
        for(size_t i = 0 ; i < n ; ++i)
        {
            if(grid[m-1][i] == 1)
            {
                q.push({m-1,i});
                vis[m-1][i] = true;
            }
            if(grid[0][i] == 1)
            {
                q.push({0,i});
                vis[0][i] = true;
            }
        }
        //进行一次bfs把与边界相连的全部改为0
        while(!q.empty())
        {
            auto [a,b] = q.front();
            q.pop();
            for(size_t i = 0 ; i < 4 ; ++i)
            {
                int y = a + dy[i] , x = b + dx[i];
                if(y >= 0 && x >= 0 && y < m && x < n && vis[y][x] == false && grid[y][x] == 1)
                {
                    q.push({y,x});
                    vis[y][x] = true;
                }
            }
        }
        int ret = 0;
        for(size_t i = 0 ; i < m ; ++i)
        {
            for(size_t j = 0 ; j < n ; ++j)
            {
                if(vis[i][j] == false && grid[i][j] == 1) ret++;
            }
        }
        return ret;
    }
};